package 图;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/6/13 17:15
 */
public class Dijkstra {









    /*
        堆优化版本的
        时间复杂度 E * lg V
        E 是 边集的个数
        V 是点集 的个数!
     */

    /**
     *
     * @param graph  整个图
     * @param source  源点(出发点)
     * @return 返回 源点 到  图上各个点的 最短路径
     */
    public int[] minDistance(HashMap<Integer, HashMap<Integer,Integer>> graph,int source){
        int n = graph.size();
        int dist[] = new int[n];
        Arrays.fill(dist,Integer.MAX_VALUE); // 把所有的点距离 初始 化 无穷大

        dist[source] = 0; // source ---> source 自己到自己的最短距离是 0

        boolean vis[] = new boolean[n];

//        PriorityQueue<Map<Integer,Integer>> queue = new PriorityQueue<>((a,b) -> a.size() - b.size());

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 按照

        // 注意 这个优先级队列里面放的到底是什么, 把这个问题理解的化, 基本上,就明白了!
        queue.add(new int[]{source,0});
        while(!queue.isEmpty()){
            int curArr[] = queue.remove();
            int curNode = curArr[0];
            int curValue = curArr[1];
            // 开始遍历邻接点
            for(Map.Entry<Integer,Integer> next : graph.get(curNode).entrySet()){
                //  这里 写 !vis[curNode]  或者 写  !vis[next.getKey()] 都能过
                if( !vis[curNode] && curValue + next.getValue() < dist[next.getKey()]){
                    /*
                     两个点:
                     - 堆里面存储的 这个 key - value 到底是什么意思!
                     - 更显 最短路径的逻辑!
                     */
                    dist[next.getKey()] = curValue + next.getValue();
                    queue.add(new int[]{next.getKey(),dist[next.getKey()]});
                }
            }
            vis[curNode] = true;  // 只要 把 curNode 当前的邻接点 给计算完毕的话, 就把当前节点给加入到, vis 数组中, 表示当前这个节点已经锁死

        }
        return dist;
    }

    /*
     不采用 堆优化的版本, 抽个时间也 手写一下吧
     */


}
